from typing import List

"""
132 的数字记为 ijk。
维护一个单调递减栈，从后往前遍历：
    若遇到比栈顶更大元素，则弹出元素，设置为 k；
    此时我们已经找到了一个 (j, k) 组合。
    继续往前遍历，若找到 nums[i] < k，则 132 模式被发现。
"""
class Solution:
    # k 来自于单调栈，因此其索引必然大于栈顶元素，其值必然小于栈顶元素
    # j 为栈顶元素
    # 当遇到 nums[i] < k 则 ik 被发现，此时 ijk 也必然成立
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []  # 单调栈维护 j
        k = -float('inf')
        for i in range(len(nums)-1, -1, -1):  # 枚举 i
            if nums[i] < k:
                return True
            # 现在 i 其实是 j
            while stack and stack[-1] < nums[i]:  # 找到了一个 (j, k)
                # 一直弹出，找到最大的 k
                k = max(k, stack.pop())
            stack.append(nums[i])
        return False
